{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %pip install numpy\n",
    "import numpy as np\n",
    "# %pip install -U scikit-learn -i https://pypi.tuna.tsinghua.edu.cn/simple\n",
    "import sklearn \n",
    "# %pip install -U matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# %pip install -U jieba -i https://pypi.tuna.tsinghua.edu.cn/simple\n",
    "import jieba\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降法求解线性回归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-0.76757629]\n",
      " [ 1.85635425]]\n"
     ]
    }
   ],
   "source": [
    "# 梯度下降法求解线性回归\n",
    "# min (Xw - y)^2, (Xw-y).T*(Xw-y)=>(w.T*X.T-y.T)*(Xw-y)\n",
    "# =>w.T*X.T*Xw - y.T*Xw - w.T*X.T*y - y.T*y\n",
    "# w一次求导： 2*w.T*X.T*X - 2*y.T*X=>2(w.T*X.T-y.T)X=>2(Xw-y).T*X\n",
    "\n",
    "learning_rate = 1e-3\n",
    "x_train = np.array([[1., 1.], [1., 2.]])\n",
    "y_train = np.array([[1.], [3.]])\n",
    "omega = np.array([[1.], [3.]])\n",
    "\n",
    "\n",
    "for i in range(5000):\n",
    "    yp = x_train.dot(omega)\n",
    "    dw = 2*((yp-y_train).T.dot(x_train)).T\n",
    "    omega -= learning_rate*dw\n",
    "\n",
    "print(omega)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.33332904]\n",
      " [1.00000265]]\n"
     ]
    }
   ],
   "source": [
    "# 岭回归\n",
    "# min (Xw - y)^2+w^2\n",
    "# w一次求导： 2(Xw-y).T*X+2*w.T\n",
    "\n",
    "learning_rate = 1e-3\n",
    "x_train = np.array([[1., 1.], [1., 2.]])\n",
    "y_train = np.array([[1.], [3.]])\n",
    "omega = np.array([[1.], [3.]])\n",
    "\n",
    "\n",
    "for i in range(5000):\n",
    "    yp = x_train.dot(omega)\n",
    "    dw = 2*((yp-y_train).T.dot(x_train)+omega.T).T\n",
    "    omega -= learning_rate*dw\n",
    "\n",
    "print(omega)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 支持向量机"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 471,
   "metadata": {},
   "outputs": [],
   "source": [
    "# class SVM:\n",
    "#     def loss(self, W, X, y, reg):\n",
    "#         train_num = X.shape[0]\n",
    "#         class_num = y.shape[0]\n",
    "#         scores = X.dot(W)\n",
    "#         loss = 0\n",
    "#         dW_total_incre = np.ones(W.shape)\n",
    "\n",
    "#         for j in range(class_num): \n",
    "#             margin = scores[:, j] - scores[np.arange(train_num),y] + 1\n",
    "#             # margin[i]表示第i组训练数据的第j个类别分数与真实类别分值的差距\n",
    "#             margin[y==j] = 0\n",
    "#             margin[margin<0] = 0\n",
    "#             loss += margin.sum()\n",
    "#             margin[margin>0] = 1\n",
    "\n",
    "#             margin[y] -= margin.sum()\n",
    "\n",
    "#             dW_total_incre[:, j] += X[margin>0].sum(axis=0)\n",
    "#             dW_total_incre[np.arange(), y] -= X[]\n",
    "\n",
    "\n",
    "#         return loss/ train_num, dW_total_incre / train_num\n",
    "\n",
    "#     def train(self, X, y):\n",
    "#         X = np.array(X)\n",
    "#         y = np.array(y)\n",
    "#         train_num = X.shape[0]\n",
    "#         feature_num = X.shape[1]\n",
    "#         class_num = y.shape[0]\n",
    "\n",
    "#         X = np.hstack([X, np.ones((train_num, 1))])\n",
    "#         W = np.random.randn(feature_num+1, class_num)*1e-2\n",
    "\n",
    "#         for i in range(2000):\n",
    "#             loss, dW = self.loss(W, X, y, None)\n",
    "#             W -= dW*1e-3\n",
    "#             if i%500 ==0:\n",
    "#                 print(\"i=\",i,\"loss=\",loss)\n",
    "\n",
    "#         print(W)\n",
    "#         self.W = W\n",
    "#         self.class_num = class_num\n",
    "    \n",
    "#     def predict(self, x):\n",
    "#         x = np.array([x])\n",
    "#         x = np.hstack([x, np.ones((1, 1))])\n",
    "#         scores = x.dot(self.W)\n",
    "#         return np.argmax(scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 435,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SVM:\n",
    "    def loss(self, W, X, y, reg):\n",
    "        train_num = X.shape[0]\n",
    "        class_num = y.shape[0]\n",
    "        scores = X.dot(W)\n",
    "        loss = 0\n",
    "        dW_total_incre = np.ones(W.shape)\n",
    "        for i in range(train_num):\n",
    "            for j in range(class_num):\n",
    "                if j == y[i]: continue\n",
    "                margin = scores[i][j] - scores[i][y[i]] + 1\n",
    "                if margin > 0:\n",
    "                    loss += margin\n",
    "                    dW_total_incre[:, j]+=X[i]\n",
    "                    dW_total_incre[:, y[i]]-=X[i]\n",
    "\n",
    "        return loss/ train_num, dW_total_incre / train_num\n",
    "\n",
    "    def train(self, X, y):\n",
    "        X = np.array(X)\n",
    "        y = np.array(y)\n",
    "        train_num = X.shape[0]\n",
    "        feature_num = X.shape[1]\n",
    "        class_num = y.shape[0]\n",
    "\n",
    "        X = np.hstack([X, np.ones((train_num, 1))])\n",
    "\n",
    "        W = np.random.randn(feature_num+1, class_num)*1e-2\n",
    "\n",
    "        for i in range(2000):\n",
    "            loss, dW = self.loss(W, X, y, None)\n",
    "            W -= dW*1e-3\n",
    "            if i%500 ==0:\n",
    "                print(\"i=\",i,\"loss=\",loss)\n",
    "\n",
    "        self.W = W\n",
    "        self.class_num = class_num\n",
    "    \n",
    "    def predict(self, x):\n",
    "        x = np.array([x])\n",
    "        x = np.hstack([x, np.ones((1, 1))])\n",
    "        scores = x.dot(self.W)\n",
    "        return np.argmax(scores)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 472,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dW_total_incre [[2. 1.]\n",
      " [2. 1.]\n",
      " [2. 1.]]\n",
      "xum[:,np.newaxis] * times[np.newaxis,:] [[1. 1.]\n",
      " [1. 1.]\n",
      " [1. 1.]]\n",
      "dW_total_incre [[1. 0.]\n",
      " [1. 0.]\n",
      " [1. 0.]]\n"
     ]
    },
    {
     "ename": "ZeroDivisionError",
     "evalue": "division by zero",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mZeroDivisionError\u001b[0m                         Traceback (most recent call last)",
      "Cell \u001b[1;32mIn[472], line 4\u001b[0m\n\u001b[0;32m      2\u001b[0m y \u001b[38;5;241m=\u001b[39m [\u001b[38;5;241m1\u001b[39m, \u001b[38;5;241m0\u001b[39m]\n\u001b[0;32m      3\u001b[0m svm \u001b[38;5;241m=\u001b[39m SVM()\n\u001b[1;32m----> 4\u001b[0m \u001b[43msvm\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mtrain\u001b[49m\u001b[43m(\u001b[49m\u001b[43mX\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43my\u001b[49m\u001b[43m)\u001b[49m \n",
      "Cell \u001b[1;32mIn[471], line 44\u001b[0m, in \u001b[0;36mSVM.train\u001b[1;34m(self, X, y)\u001b[0m\n\u001b[0;32m     41\u001b[0m W \u001b[38;5;241m=\u001b[39m np\u001b[38;5;241m.\u001b[39mrandom\u001b[38;5;241m.\u001b[39mrandn(feature_num\u001b[38;5;241m+\u001b[39m\u001b[38;5;241m1\u001b[39m, class_num)\u001b[38;5;241m*\u001b[39m\u001b[38;5;241m1e-2\u001b[39m\n\u001b[0;32m     43\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m2000\u001b[39m):\n\u001b[1;32m---> 44\u001b[0m     loss, dW \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mloss\u001b[49m\u001b[43m(\u001b[49m\u001b[43mW\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mX\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43my\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43;01mNone\u001b[39;49;00m\u001b[43m)\u001b[49m\n\u001b[0;32m     45\u001b[0m     W \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m=\u001b[39m dW\u001b[38;5;241m*\u001b[39m\u001b[38;5;241m1e-3\u001b[39m\n\u001b[0;32m     46\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m i\u001b[38;5;241m%\u001b[39m\u001b[38;5;241m500\u001b[39m \u001b[38;5;241m==\u001b[39m\u001b[38;5;241m0\u001b[39m:\n",
      "Cell \u001b[1;32mIn[471], line 29\u001b[0m, in \u001b[0;36mSVM.loss\u001b[1;34m(self, W, X, y, reg)\u001b[0m\n\u001b[0;32m     27\u001b[0m     dW_total_incre \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m=\u001b[39m xum[:,np\u001b[38;5;241m.\u001b[39mnewaxis] \u001b[38;5;241m*\u001b[39m times[np\u001b[38;5;241m.\u001b[39mnewaxis,:]\n\u001b[0;32m     28\u001b[0m     \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mdW_total_incre\u001b[39m\u001b[38;5;124m\"\u001b[39m, dW_total_incre)\n\u001b[1;32m---> 29\u001b[0m     \u001b[38;5;241;43m1\u001b[39;49m\u001b[38;5;241;43m/\u001b[39;49m\u001b[38;5;241;43m0\u001b[39;49m\n\u001b[0;32m     31\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m loss\u001b[38;5;241m/\u001b[39m train_num, dW_total_incre \u001b[38;5;241m/\u001b[39m train_num\n",
      "\u001b[1;31mZeroDivisionError\u001b[0m: division by zero"
     ]
    }
   ],
   "source": [
    "X = [[1,1],[0,0]]\n",
    "y = [1, 0]\n",
    "svm = SVM()\n",
    "svm.train(X, y) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 308,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "x = [2,2]\n",
    "print(svm.predict(x))\n",
    "x = [-1,-1]\n",
    "print(svm.predict(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 朴素贝叶斯"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 朴素贝叶斯检测垃圾邮件\n",
    "import re\n",
    "import os\n",
    "\n",
    "def find_word_index(vocab, word):\n",
    "    left, right = 0, len(vocab)-1\n",
    "    while left<=right:\n",
    "        mid =(left+right)//2\n",
    "        if vocab[mid] == word:\n",
    "            return mid\n",
    "        elif vocab[mid]>word:\n",
    "            right = mid-1\n",
    "        else:\n",
    "            left = mid+1\n",
    "\n",
    "\n",
    "def word2vec(vocab, words):\n",
    "    vec = [0]*len(vocab)\n",
    "    for word in words:\n",
    "        vec[find_word_index(vocab, word)] = 1\n",
    "    return vec\n",
    "\n",
    "\n",
    "def file2word(filepath):\n",
    "    with open(filepath, encoding=\"UTF-8\", mode=\"r\")as f:\n",
    "        s = f.read()\n",
    "        return list(jieba.cut(s, cut_all=False))\n",
    "\n",
    "def read_filewords_in_dir(dirpath:str):\n",
    "    prepath=dirpath\n",
    "    filewords = []\n",
    "    if not prepath.endswith(\"/\"): prepath += \"/\"\n",
    "    count = 0\n",
    "    for file in os.listdir(dirpath):\n",
    "        filepath=prepath+file\n",
    "        filewords.append(file2word(filepath))\n",
    "\n",
    "        count+=1\n",
    "        if count>500:\n",
    "            break\n",
    "\n",
    "    return filewords\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [],
   "source": [
    "ham_filewords = read_filewords_in_dir(\"./data_set/ham_all/\")\n",
    "spam_filewords = read_filewords_in_dir(\"./data_set/spam_all/\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab_set = set()\n",
    "\n",
    "for file in ham_filewords:\n",
    "    for word in file:\n",
    "        vocab_set.add(word)\n",
    "\n",
    "for file in spam_filewords:\n",
    "    for word in file:\n",
    "        vocab_set.add(word)  \n",
    "\n",
    "vocab = list(vocab_set)  \n",
    "vocab = sorted(vocab)\n",
    "\n",
    "X = [] \n",
    "for fileword in ham_filewords:\n",
    "    X.append(word2vec(vocab, fileword))\n",
    "\n",
    "for fileword in spam_filewords:\n",
    "    X.append(word2vec(vocab, fileword))\n",
    "\n",
    "y = [0]*len(ham_filewords) + [1]*len(spam_filewords)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 贝叶斯分类\n",
    "import math\n",
    "\n",
    "class BYS:\n",
    "    def __init__(self):\n",
    "        self.spam_num = None \n",
    "        self.ham_num = None\n",
    "        self.total_num = None\n",
    "        self.spam_word_count = None\n",
    "        self.ham_word_count = None\n",
    "        self.word_count = None\n",
    "\n",
    "    def train(self, X, y):\n",
    "        X = np.array(X)\n",
    "        y = np.array(y)\n",
    "\n",
    "        ham_word_count = X[y==0].sum(0)\n",
    "        ham_num = (y==0).sum()\n",
    "        spam_word_count = X[y==1].sum(0)\n",
    "        spam_num = (y==1).sum()\n",
    "        word_count = ham_word_count+spam_word_count\n",
    "\n",
    "        self.spam_num = spam_num \n",
    "        self.ham_num = ham_num\n",
    "        self.total_num = spam_num+ham_num\n",
    "        self.spam_word_count = spam_word_count\n",
    "        self.ham_word_count = ham_word_count\n",
    "        self.word_count = word_count\n",
    "\n",
    "    def predict(self, x):\n",
    "        x = np.array(x)\n",
    "        sp = np.copy(self.spam_word_count[x==1])\n",
    "        sp[sp==0]=1\n",
    "        spam_log_sum = np.log(sp * self.total_num).sum()\n",
    "        tt = np.copy(self.word_count[x==1])\n",
    "        tt[tt==0]=1\n",
    "        total_log_sum =  np.log(tt * self.spam_num).sum()\n",
    "\n",
    "        # p*exp log  mutil(s/sn)/mutil(t/tn)) \n",
    "        # => p*exp(log(mutil (s*tn)/ (sn*t)))\n",
    "        # => p*exp(sum(log (s*tn)/ (sn*t)))\n",
    "        # => p*exp(sum(log (s*tn)- log(sn*t)))\n",
    "        return self.spam_num/self.total_num * math.exp(spam_log_sum-total_log_sum)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "bys = BYS()\n",
    "bys.train(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.480368380779051e-23\n",
      "4.7022256062132306e+30\n"
     ]
    }
   ],
   "source": [
    "print(bys.predict(X[0]))\n",
    "print(bys.predict(X[-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 高斯朴素贝叶斯分类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 309,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 高斯朴素贝叶斯分类\n",
    "import math\n",
    "\n",
    "class GSBYS:\n",
    "    def train(self, X, y):\n",
    "        X = np.array(X)\n",
    "        y = np.array(y)\n",
    "\n",
    "        self.theta=np.ones((3, X.shape[1]))\n",
    "        self.theta[0] = X[y==0].std(axis=0)\n",
    "        self.theta[1] = X[y==1].std(axis=0)\n",
    "        self.theta[2] = X.std(axis=0)\n",
    "        self.theta[self.theta==0] = 1e-6\n",
    "\n",
    "        self.mu =np.ones((3, X.shape[1]))\n",
    "        self.mu[0] = X[y==0].mean(axis=0)\n",
    "        self.mu[1] = X[y==1].mean(axis=0)\n",
    "        self.mu[2] = X.mean(axis=0)\n",
    "\n",
    "        spam_gs_meup = -np.pow(X-self.mu[2], 2)/(2*np.pow(self.theta[2], 2))\n",
    "\n",
    "        ham_num = (y==0).sum()\n",
    "        spam_num = (y==1).sum()\n",
    "\n",
    "        self.spam_num = spam_num \n",
    "        self.ham_num = ham_num\n",
    "        self.total_num = spam_num+ham_num\n",
    "        self.spam_gs_meup = spam_gs_meup\n",
    "\n",
    "    def predict(self, x):\n",
    "        x = np.array(x)\n",
    "        spam_gs_seup = -np.pow(x-self.mu[1], 2)/(2*np.pow(self.theta[1], 2))\n",
    "        spam_seup_sum = spam_gs_seup.sum()\n",
    "        total_seup_sum = self.spam_gs_meup.sum()\n",
    "        print(-np.log(self.theta[1]).sum(), -np.log(self.theta[2]).sum())\n",
    "        return self.spam_num/self.total_num * np.exp(-np.log(self.theta[1]).sum() +spam_seup_sum + np.log(self.theta[2]).sum() - total_seup_sum) \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [],
   "source": [
    "gsbys = GSBYS()\n",
    "gsbys.train(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 259,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "150174.19465029115 49596.42976601038\n",
      "0.0\n",
      "150174.19465029115 49596.42976601038\n",
      "inf\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\31538\\AppData\\Local\\Temp\\ipykernel_7948\\230476102.py:36: RuntimeWarning: overflow encountered in exp\n",
      "  return self.spam_num/self.total_num * np.exp(-np.log(self.theta[1]).sum() +spam_seup_sum + np.log(self.theta[2]).sum() - total_seup_sum)\n"
     ]
    }
   ],
   "source": [
    "print(gsbys.predict(X[0]))\n",
    "print(gsbys.predict(X[-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0.]]\n",
      "[[0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "from sklearn import datasets\n",
    "iris = datasets.load_iris()\n",
    "from sklearn.naive_bayes import GaussianNB\n",
    "gnb = GaussianNB()\n",
    "gnb.fit(X, y)\n",
    "print(gnb.predict_proba([X[0]]))\n",
    "print(gnb.predict_proba([X[-1]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ID3：Gain(D, X) = Ent(D) - Ent(D|X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 720,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Answer:\n",
    "    def __init__(self):\n",
    "        self.results = []\n",
    "\n",
    "    def add(self, result, p):\n",
    "        self.results.append((result, p))\n",
    "\n",
    "    def __str__(self):\n",
    "        s=\"[\"\n",
    "        for item in self.results:\n",
    "            s+=\"{reuslt:\"+str(item[0])+\", p:\"+str(item[1])+\"},\"\n",
    "        s+=\"]\"\n",
    "        return s\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self):\n",
    "        self.paths = []\n",
    "        self.feature_index = None\n",
    "    \n",
    "    def add_path(self, path):\n",
    "        self.paths.append(path)\n",
    "\n",
    "    def __str__(self):\n",
    "        path_str=\"[\"\n",
    "        for path in self.paths:\n",
    "            path_str+=str(path)+\", \"\n",
    "        path_str+=\"]\"\n",
    "        return \"{paths:\"+path_str+\", feature_index:\"+str(self.feature_index)+\"}\"\n",
    "\n",
    "class NodePath:\n",
    "    def __init__(self, cls_value, treeNode, answer):\n",
    "        self.cls_value = cls_value\n",
    "        self.treeNode = treeNode\n",
    "        self.answer = answer\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"{cls_value:\"+str(self.cls_value)+\", treeNode:\"+str(self.treeNode)+\", answer:\"+str(self.answer)+\"}\"\n",
    "\n",
    "class ID3DecisionTree:\n",
    "    def ent(self, D):\n",
    "        fre = np.bincount(D)+1\n",
    "        p = fre / fre.sum()\n",
    "        return -np.multiply(p, np.log(p)).sum()\n",
    "\n",
    "    def gain(self, D, X):\n",
    "        cnts = np.bincount(X)\n",
    "        entdx = 0 \n",
    "        for i in range(cnts.shape[0]):\n",
    "            entdx += self.ent(D[X==i])\n",
    "        return self.ent(D) - entdx \n",
    "    \n",
    "    # 递归建立\n",
    "    def build(self, last_cls_value, X, y, visited)->TreeNode|Answer:\n",
    "        result_values = np.unique(y)\n",
    "        # print(\"   \"*len(visited)+\"last_cls_value:\"+str(last_cls_value)+\" result_values\",result_values)\n",
    "        if result_values.shape[0] == 1:\n",
    "            # 仅剩一个结果\n",
    "            # for i in range(X.shape[0]):\n",
    "            #     if i not in visited:\n",
    "            #         print(\"   \"*(len(visited)+1)+\" cansure \"+ str(i))\n",
    "            #         break\n",
    "            ans = Answer()\n",
    "            ans.add(y[0], 1)\n",
    "            return ans\n",
    "   \n",
    "        feature_num = X.shape[1]\n",
    "\n",
    "        if feature_num == len(visited):\n",
    "            # 如果已经没有剩余特征了\n",
    "            cls_count = np.bincount(y)\n",
    "            p = cls_count/cls_count.sum()\n",
    "            ans = Answer()\n",
    "            for i in range(cls_count.shape[0]):\n",
    "                if cls_count[i]!=0:\n",
    "                    ans .add(cls_count[i], p[i])\n",
    "            return ans\n",
    "\n",
    "        # 找出熵减最大的\n",
    "        max_feature_index =0\n",
    "        max_gain = float(\"-inf\")\n",
    "        for i in range(feature_num):\n",
    "            if i in visited: continue\n",
    "\n",
    "            g = self.gain(y, X[:, i])\n",
    "            if g>max_gain:\n",
    "                max_gain = g\n",
    "                max_feature_index = i\n",
    "\n",
    "        root = TreeNode()\n",
    "        root.feature_index = max_feature_index\n",
    "        # 递归建立剩余特征\n",
    "        visited.append(max_feature_index)\n",
    "        cls_values = np.unique(X[:, max_feature_index])\n",
    "        # print(\"   \"*len(visited)+\"max_feature_index=\",max_feature_index)\n",
    "        for value in cls_values:\n",
    "            rows_take = X[:, max_feature_index]==value\n",
    "            childNode = self.build(value, X[rows_take], y[rows_take], visited)\n",
    "            path = None\n",
    "            if type(childNode)==TreeNode:\n",
    "                path = NodePath(value, childNode, None)\n",
    "            elif type(childNode)==Answer:\n",
    "                path = NodePath(value, None, childNode)\n",
    "            else:\n",
    "                raise Exception(\"illegal type\")\n",
    "            root.add_path(path)\n",
    "        visited.remove(max_feature_index)\n",
    "\n",
    "        return root\n",
    "\n",
    "    def train(self, X, y):\n",
    "        X = np.array(X)\n",
    "        y = np.array(y)\n",
    "        self.root = TreeNode()\n",
    "        visited = []\n",
    "        self.root = self.build(None, X, y, visited)\n",
    "\n",
    "    def predict(self, x):\n",
    "        x = np.array(x)\n",
    "        nd = self.root\n",
    "        while True:\n",
    "            # print(\"curr feature_index=\", nd.feature_index)\n",
    "            assert nd.feature_index is not None\n",
    "            assert nd.paths is not None and len(nd.paths)>0\n",
    "\n",
    "            for path in nd.paths:\n",
    "                # print(\"     feature_index=\",nd.feature_index,\"path.cls_value=\", path.cls_value, \"x[nd.feature_index]=\", x[nd.feature_index])                \n",
    "                if path.cls_value == x[nd.feature_index]:\n",
    "                    # print(\"        path.answer\", path.answer)\n",
    "                    if path.answer is not None:\n",
    "                        # print(\"path.answer=\", path.answer)\n",
    "                        return path.answer\n",
    "                    else: \n",
    "                        nd = path.treeNode\n",
    "                        break\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 550,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-0.6517565611726531\n"
     ]
    }
   ],
   "source": [
    "print(9/14*math.log(9/14) + 5/14*math.log(5/14))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 729,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{paths:[{cls_value:0, treeNode:{paths:[{cls_value:0, treeNode:None, answer:[{reuslt:1, p:1},]}, {cls_value:1, treeNode:{paths:[{cls_value:0, treeNode:None, answer:[{reuslt:0, p:1},]}, {cls_value:1, treeNode:None, answer:[{reuslt:1, p:1},]}, {cls_value:2, treeNode:None, answer:[{reuslt:1, p:1},]}, ], feature_index:0}, answer:None}, ], feature_index:3}, answer:None}, {cls_value:1, treeNode:{paths:[{cls_value:0, treeNode:{paths:[{cls_value:1, treeNode:{paths:[{cls_value:0, treeNode:None, answer:[{reuslt:1, p:1},]}, {cls_value:2, treeNode:None, answer:[{reuslt:0, p:1},]}, ], feature_index:0}, answer:None}, {cls_value:2, treeNode:{paths:[{cls_value:1, treeNode:None, answer:[{reuslt:1, p:1},]}, {cls_value:2, treeNode:None, answer:[{reuslt:1, p:0.5},{reuslt:1, p:0.5},]}, ], feature_index:0}, answer:None}, ], feature_index:1}, answer:None}, {cls_value:1, treeNode:{paths:[{cls_value:0, treeNode:None, answer:[{reuslt:0, p:1},]}, {cls_value:1, treeNode:None, answer:[{reuslt:1, p:1},]}, {cls_value:2, treeNode:None, answer:[{reuslt:0, p:1},]}, ], feature_index:0}, answer:None}, ], feature_index:3}, answer:None}, ], feature_index:2}\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[2,\t2,\t1,\t0],\n",
    "              [2,\t2,\t1,\t0],\n",
    "                [2,\t2,\t1,\t1],\n",
    "                [1,\t2,\t1,\t0],\n",
    "                [0,\t1,\t1,\t0],\n",
    "                [0,\t0,\t0,\t0],\n",
    "                [0,\t0,\t0,\t1],\n",
    "                [1,\t0,\t0,\t1],\n",
    "                [2,\t1,\t1,\t0],\n",
    "                [2,\t0,\t0,\t0],\n",
    "                [0,\t1,\t0,\t0],\n",
    "                [2,\t1,\t0,\t1],\n",
    "                [1,\t1,\t1,\t1],\n",
    "                [1,\t2,\t0,\t0],\n",
    "                [0,\t1,\t1,\t1]])\n",
    "y = np.array([0,1,0,1,1,1,0,1,0,1,1,1,1,1,0])\n",
    "tree = ID3DecisionTree()\n",
    "tree.train(X, y)\n",
    "print(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 730,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{reuslt:1, p:0.5},{reuslt:1, p:0.5},]\n"
     ]
    }
   ],
   "source": [
    "print(tree.predict(X[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 贝叶斯岭回归作图\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def func(x):\n",
    "    return np.sin(2 * np.pi * x)\n",
    "\n",
    "\n",
    "size = 25\n",
    "rng = np.random.RandomState(1234)\n",
    "x_train = rng.uniform(0.0, 1.0, size)\n",
    "y_train = func(x_train) + rng.normal(scale=0.1, size=size)\n",
    "x_test = np.linspace(0.0, 1.0, 100)\n",
    "\n",
    "from sklearn.linear_model import BayesianRidge\n",
    "\n",
    "n_order = 3\n",
    "X_train = np.vander(x_train, n_order + 1, increasing=True)\n",
    "X_test = np.vander(x_test, n_order + 1, increasing=True)\n",
    "reg = BayesianRidge(tol=1e-6, fit_intercept=False, compute_score=True)\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=(8, 4))\n",
    "for i, ax in enumerate(axes):\n",
    "    # Bayesian ridge regression with different initial value pairs\n",
    "    if i == 0:\n",
    "        init = [1 / np.var(y_train), 1.0]  # Default values\n",
    "    elif i == 1:\n",
    "        init = [1.0, 1e-3]\n",
    "        reg.set_params(alpha_init=init[0], lambda_init=init[1])\n",
    "    reg.fit(X_train, y_train)\n",
    "    ymean, ystd = reg.predict(X_test, return_std=True)\n",
    "\n",
    "    ax.plot(x_test, func(x_test), color=\"blue\", label=\"sin($2\\\\pi x$)\")\n",
    "    ax.scatter(x_train, y_train, s=50, alpha=0.5, label=\"observation\")\n",
    "    ax.plot(x_test, ymean, color=\"red\", label=\"predict mean\")\n",
    "    ax.fill_between(\n",
    "        x_test, ymean - ystd, ymean + ystd, color=\"pink\", alpha=0.5, label=\"predict std\"\n",
    "    )\n",
    "    ax.set_ylim(-1.3, 1.3)\n",
    "    ax.legend()\n",
    "    title = \"$\\\\alpha$_init$={:.2f},\\\\ \\\\lambda$_init$={}$\".format(init[0], init[1])\n",
    "    if i == 0:\n",
    "        title += \" (Default)\"\n",
    "    ax.set_title(title, fontsize=12)\n",
    "    text = \"$\\\\alpha={:.1f}$\\n$\\\\lambda={:.3f}$\\n$L={:.1f}$\".format(\n",
    "        reg.alpha_, reg.lambda_, reg.scores_[-1]\n",
    "    )\n",
    "    ax.text(0.05, -1.0, text, fontsize=12)\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
